/*-- buddy_pmm.c --*/
#include <pmm.h>
#include <list.h>
#include <string.h>
#include <buddy_pmm.h>
#include<stdio.h>

// 根据完全二叉树性质，定义左右孩子和父节点索引关系
#define LEFT_CHILD(index)   ((index) << 1)
#define RIGHT_CHILD(index)  (((index) << 1) + 1)
#define PARENT(index)       ((index) >> 1)
#define IS_POWER_OF_2(x)    (!((x) & ((x) - 1)))
#define MAX(a, b)           ((a) > (b) ? (a) : (b))
// 深度设置为30,最大可分配内存大小为2^29，即大约1GiB
#define BUDDY_MAX_DEPTH 30

// 全局变量
static unsigned int* buddy_page;      // Buddy System使用的二叉树结构，用来描述内存情况
static unsigned int buddy_page_num;        //管理页数量
static unsigned int useable_page_num;      //可用页数量
static struct Page* useable_page_base;     //可用页基址

static void
buddy_init(void) {
    /* do nothing */
}

static void
buddy_init_memmap(struct Page *base, size_t n) {
    // 检查参数
    assert((n > 0));
    // 获得伙伴系统的各参数
    // 可使用内存页数 && 管理内存页数
    useable_page_num = 1;
    for (int i = 1;(i < BUDDY_MAX_DEPTH) ;  i++)
    {
        if((useable_page_num + (useable_page_num /512) >= n))break;
    useable_page_num*=2 ;
    }
    //上方设置了关于n的2的向上取整次幂个页，太多了，因此我们要再除一下，否则分配的页的大小大于实际大小
    useable_page_num /= 2;

    buddy_page_num = (useable_page_num /512) + 1;
        // 可使用内存页基址  = 基址 + 管理页数
    useable_page_base = base + buddy_page_num;
    // 初始化所有页
      // 管理页（0～buddy_page_num-1）权限初始化
    for (int i = 0; i <buddy_page_num; i++){
        SetPageReserved(base + i);
    }
    // 可使用页（buddy_page_num～n）权限初始化
    for (int i = buddy_page_num; i <n; i++){
        ClearPageReserved(base + i);
        SetPageProperty(base + i);
        set_page_ref(base + i, 0);
    }
    // 总共有useable_page_num个页面，树的叶节点就是下标为useable_page_num~2*useable_page_num-1 之间
    buddy_page = (unsigned int*)KADDR(page2pa(base));
    // 先初始最底层的部分，它们的大小均为2^0=1
    for (int i = useable_page_num; i < useable_page_num *2; i++){
        buddy_page[i] = 1;
    }
    // 再初始上层的部分，根据二叉树性质进行，父节点就是子节点的二倍
    for (int i = useable_page_num - 1; i > 0; i--){
        buddy_page[i] = buddy_page[LEFT_CHILD(i)] << 1;
    }
    // 输出信息
    cprintf("buddy init: Total %d, Buddy %d, Useable %d\n",
            n, buddy_page_num, useable_page_num);
}

static struct
Page* buddy_alloc_pages(size_t n) {
    // 检查参数
    assert(n > 0);
    // 需要的页数太大, 返回NULL(分配失败)；这里buddy_page[1]表示最大的大小
    if (n > buddy_page[1]){
        return NULL;
    }
    // 找到需要的页区
    unsigned int index = 1;
    while(1){
        if (buddy_page[LEFT_CHILD(index)] >= n){
            index = LEFT_CHILD(index);
        }
        else if (buddy_page[RIGHT_CHILD(index)] >= n){
            index = RIGHT_CHILD(index);
        }
        else{
            break;
        }
    }
    // 分配页面
    unsigned int size = buddy_page[index];
    buddy_page[index] = 0;//首先将这个页置为0表示已经分配走了，因为一旦分配则是按照2的整数次幂分配，则该处页的可分配大小变为0

    struct Page* new_page = &useable_page_base[index * size - useable_page_num];
    // 从new_page~new_page+size这个范围的内存空间已经被分配，所以设置属性值
    for (struct Page* p = new_page; p != new_page + size; p++)
    {
        ClearPageProperty(p);
        set_page_ref(p, 0);
    }
    // 更新上方节点可支配的内存大小
    index = PARENT(index);
    while(index > 0){
        buddy_page[index] = MAX(buddy_page[LEFT_CHILD(index)], buddy_page[RIGHT_CHILD(index)]);
        index = PARENT(index);
    }
    // 返回分配到的page
    return new_page;
}

static void
buddy_free_pages(struct Page *base, size_t n) {
    // 检查参数
    assert(n > 0);
    // 释放
    for (struct Page *p = base; p != base + n; p++) {
        assert(!PageReserved(p) && !PageProperty(p));
        SetPageProperty(p);
        set_page_ref(p, 0);
    }
    // 维护
    unsigned int index = useable_page_num + (unsigned int)(base - useable_page_base), size = 1;
    while(buddy_page[index] > 0){
        index=PARENT(index);
        size = size*2;
    }
    //free了，所以要维护节点可以操纵的内存数量
    buddy_page[index] = size;
    while((index = PARENT(index)) > 0){
        size = size*2;
        // 当左右孩子之和=size时，说明左右孩子此时均未被分配、从而可以合并
        if(buddy_page[LEFT_CHILD(index)] + buddy_page[RIGHT_CHILD(index)] == size){
            buddy_page[index] = size;
        }
        else{
            buddy_page[index] = MAX(buddy_page[LEFT_CHILD(index)], buddy_page[RIGHT_CHILD(index)]);
        }
    }
}

static size_t
buddy_nr_free_pages(void) {
    return buddy_page[1];
}

// 测试1
static void
buddy_check(void) {
    struct Page* p0=NULL,*p1=NULL,*p2=NULL,*p3=NULL,*p4=NULL,*p5=NULL,*p6=NULL;
    p0=alloc_pages(1);
    assert(p0!=NULL);//确保p0有被分到页
    p1=alloc_pages(2);
    assert(p1!=NULL);//确保p1有分到页
    assert(p0+2==p1)//如上第一点
        
    p3=alloc_pages(1);
    assert(p3!=NULL);
    assert(p3==p0+1);//如上第2点
    p4=alloc_pages(2);
    p5=alloc_pages(2);
    p6=alloc_pages(7);
//检查p6是否被分配8单位。，如上第三点
    assert(p6!=NULL&&!PageProperty(p6)&&!PageProperty(p6+7)&&PageProperty(p6+8));

    free_pages(p3,1)//释放p3
    assert(PageProperty(p3))//检查p3确实被释放了
    free_pages(p4,2);
    free_pages(p5,2);
    free_pages(p6,8);
    assert((p6+7)->ref==0);//检查确实释放，如上第四点
    
    p2=alloc_pages(3);
    assert(p3!=NULL&&p1+4==p2&&!PageProperty(p2+3));//再次重新分配内存，查看之前的内存是否释放干净,如上4
    free_pages(p2,4);
    free_pages(p0,1);
        
}

// 测试2
/*
static void
buddy_check(void) {
    int all_pages = nr_free_pages();
    struct Page* p0, *p1, *p2, *p3;
    // 分配过大的页数
    assert(alloc_pages(all_pages + 1) == NULL);
    // 分配两个组页
    p0 = alloc_pages(3);     // 分配了4给p0
    assert(p0 != NULL);
    p1 = alloc_pages(7);     // 分配了8给p1
    assert(p1 == p0 + 8);
    assert(!PageReserved(p0) && !PageProperty(p0));
    assert(!PageReserved(p1) && !PageProperty(p1));
    // 再分配两个组页
    p2 = alloc_pages(1);     // 分配了1给p2
    assert(p2 == p0 + 4);
    p3 = alloc_pages(5);     // 分配了8给p3
    assert(p3 == p0 + 16);
    assert(!PageProperty(p3) && !PageProperty(p3 + 7) && PageProperty(p3 + 8));
    // 回收页
    free_pages(p1, 7);       // 未发生合并
    assert(PageProperty(p1) && PageProperty(p1 + 1));
    assert(p1->ref == 0);
    free_pages(p0, 3);       // 未发生合并
    free_pages(p2, 1);       // 向右与1合并，向右与2合并，向左与4合并，向右与8合并
    // 回收后再分配
    p2 = alloc_pages(13);    //分配16给p2
    assert(p2 == p0);        //此时p2位于最左边
    free_pages(p2, 13);
    assert((p2 + 2)->ref == 0);
    assert(nr_free_pages() == all_pages >> 1);
    p1 = alloc_pages(7);     // 分配8给p1
    p2 = alloc_pages(3);     // 分配4给p2
    assert(p1 == p0);
    assert(p2 == p0 + 8);
    free_pages(p1, 7);
    free_pages(p2, 3);
    free_pages(p3, 5);
}
*/

const struct pmm_manager buddy_pmm_manager = {
    .name = "buddy_pmm_manager",
    .init = buddy_init,
    .init_memmap = buddy_init_memmap,
    .alloc_pages = buddy_alloc_pages,
    .free_pages = buddy_free_pages,
    .nr_free_pages = buddy_nr_free_pages,
    .check = buddy_check,
};